import { DoublyNode } from "./LinkedNode";
import { LinkedList } from "./01_实现单向链表LinkedList";

interface IDoublyLinkedList<T> {
  append(value: T): void; // 在链表尾部添加一个新的项
  prepend(value: T): void; // 在链表头部添加一个新的项
  postTraverse(): void; // 从尾到头遍历链表
  insert(value: T, position: number): boolean; // 向链表的特定位置插入一个新的项
  removeAt(position: number): T | null; // 从链表的特定位置移除一项
}

class DoublyLinkedList<T>
  extends LinkedList<T>
  implements IDoublyLinkedList<T>
{
  protected head: DoublyNode<T> | null = null;
  protected tail: DoublyNode<T> | null = null;
  append(value: T): void {
    const node = new DoublyNode<T>(value);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail!.next = node;
      this.tail = node;
    }
    this.size++;
  }
  prepend(value: T): void {
    const node = new DoublyNode<T>(value);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      const current = this.head;
      current.prev = node;
      current.prev.next = current;
      this.head = node;
    }
    this.size++;
  }
  insert(value: T, position: number): boolean {
    if (position < 0 || position > this.size) return false;
    if (position === 0) {
      this.prepend(value);
    } else if (position === this.size - 1) {
      this.append(value);
    } else {
      const newNode = new DoublyNode<T>(value);
      const current = this._getNode(position) as DoublyNode<T>;

      newNode.prev = current!.prev;
      newNode.next = current;
      current!.prev!.next = newNode;
      current!.prev = newNode;
      this.size++;
    }

    return true;
  }
  postTraverse(): void {
    if (!this.head) {
      return;
    }
    let current = this.tail;
    let values: T[] = [];
    while (current) {
      values.push(current.value);
      current = current.prev;
    }
    console.log(values.join("->"));
  }
}

const dll = new DoublyLinkedList<string>();
dll.append("aaa");
dll.append("bbb");
dll.append("ccc");
dll.traverse();

console.log("----- prepend -----");
dll.prepend("ddd");
dll.traverse();

export { DoublyLinkedList };
